package algotithm.leetcode.dfs.test39;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author zhouyanxiang
 * @Date 2021-04-2021/4/11-23:51
 * @Title 39. 组合总和
 *
 */
public class Solution {

    public static void main(String[] args) {
       int[] candidates = {2,3,6,7};
       int target = 7;
       Solution solution = new Solution();
        List<List<Integer>> lists = solution.combinationSum(candidates, target);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> list = new ArrayList<>();
        if(len == 0) {
            return list;
        }
        Deque<Integer> path =  new ArrayDeque<>();
        dfs(candidates,0,len,target,path,list);
        return list;
    }

    public void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> list) {
        if(len == 0) {
            return;
        }
        if(target < 0) {
            return;
        }
        if(target == 0) {
            list.add(new ArrayList<>(path));
            return;
        }
        for(int i = begin;i < len;i++) {
            path.addLast(candidates[i]);
            dfs(candidates,i,len,target-candidates[i],path,list);
            path.removeLast();
        }
    }
}
